package 算法基础模板.chapter_03;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <pre>{@code
 *  // 求最短路问题
 *  queue<int> q;
 *   st[1] = true; // 表示1号点已经被遍历过
 *   q.push(1);
 *
 *   while (q.size())
 *   {
 *       int t = q.front();
 *       q.pop();
 *
 *       for (int i = h[t]; i != -1; i = ne[i])
 *       {
 *           int j = e[i];
 *           if (!st[j])
 *           {
 *               st[j] = true; // 表示点j已经被遍历过
 *               q.push(j);
 *           }
 *       }
 *   }
 * }</pre>
 *
 * @author Summerday
 */
public class BFS {

    Queue<int[]> q = new LinkedList<>();
    int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
    int m, n;
    int[][] matrix;
    int[][] d;

    int bfs () {
        q.add(new int[]{0, 0});
        while (!q.isEmpty()) {
            int[] e = q.poll();
            for (int i = 0; i < 4; i++) {
                int x = dx[i] + e[0];
                int y = dy[i] + e[1];
                if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] == 0 && d[x][y] == -1) {
                    d[x][y] = d[e[0]][e[1]] + 1;
                    q.offer(new int[]{x, y});
                }

            }
        }
        return d[m - 1][n - 1];
    }

}
